<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="GspaD" id="GspaD"><span data-lake-id="u49a933c0" id="u49a933c0">典型回答</span></h1>
  <p data-lake-id="uaaa754a9" id="uaaa754a9"><br></p>
  <p data-lake-id="ua5d426e2" id="ua5d426e2"><strong><span data-lake-id="u4901369e" id="u4901369e">三色标记算法是一种JVM中垃圾标记的算法，他可以减少JVM在GC过程中的STW时长，他是CMS、G1等垃圾收集器中主要使用的标记算法。</span></strong></p>
  <p data-lake-id="u969479e1" id="u969479e1"><span data-lake-id="u4101ac4e" id="u4101ac4e">​</span><br></p>
  <p data-lake-id="u69ba1e3e" id="u69ba1e3e"><span data-lake-id="udb285e15" id="udb285e15">在出现三色标记算法之前，JVM中垃圾对象的标记主要采用可达性分析算法及引用计数法。但是这两种算法存在以下问题：</span></p>
  <p data-lake-id="uf0c415c1" id="uf0c415c1"><span data-lake-id="u4436ce6f" id="u4436ce6f">​</span><br></p>
  <p data-lake-id="uaa26fdb1" id="uaa26fdb1"><span data-lake-id="u2152291b" id="u2152291b">1、</span><strong><span data-lake-id="ua6a7a2c3" id="ua6a7a2c3">循环引用问题</span></strong><span data-lake-id="u2cac82e3" id="u2cac82e3">，如果两个对象互相引用，就形成了一个环形结构，如果采用引用计数法的话，那么这两个对象将永远无法被回收。</span></p>
  <p data-lake-id="u61bced63" id="u61bced63"><span data-lake-id="ucf2ecc3f" id="ucf2ecc3f">​</span><br></p>
  <p data-lake-id="ueecb1adc" id="ueecb1adc"><span data-lake-id="u453fe7dd" id="u453fe7dd">2、</span><strong><span data-lake-id="u119f4aa7" id="u119f4aa7">STW时间长</span></strong><span data-lake-id="udb78c5c0" id="udb78c5c0">，可达性分析的整个过程都需要STW，以避免对象的状态发生改变，这就导致GC停顿时长很长，大大影响应用的整体性能。</span></p>
  <p data-lake-id="u2a152c4f" id="u2a152c4f"><br></p>
  <p data-lake-id="ua1cf2067" id="ua1cf2067"><span data-lake-id="u1caaf134" id="u1caaf134">为了解决上面这些问题，就引入了</span><strong><span data-lake-id="u61fddb7d" id="u61fddb7d">三色标记法</span></strong><span data-lake-id="uf1e41d72" id="uf1e41d72">。</span></p>
  <p data-lake-id="ufd47183e" id="ufd47183e"><span data-lake-id="u8af05226" id="u8af05226">​</span><br></p>
  <p data-lake-id="u5328509c" id="u5328509c"><strong><span data-lake-id="u818a6dd7" id="u818a6dd7">三色标记法将对象分为三种状态：白色、灰色和黑色。</span></strong></p>
  <p data-lake-id="ue6ace710" id="ue6ace710"><span data-lake-id="u84fc9105" id="u84fc9105">​</span><br></p>
  <p data-lake-id="u90373cf9" id="u90373cf9"><span data-lake-id="u275f53e8" id="u275f53e8">白色：</span><span data-lake-id="ua89f5b1e" id="ua89f5b1e" class="lake-fontsize-12" style="color: rgb(37, 41, 51)">该对象没有被标记过。</span></p>
  <p data-lake-id="u6f68f625" id="u6f68f625"><span data-lake-id="u9b436869" id="u9b436869">灰色：</span><span data-lake-id="ufe9b1833" id="ufe9b1833" class="lake-fontsize-12" style="color: rgb(37, 41, 51)">该对象已经被标记过了，但该对象的引用对象还没标记完。</span></p>
  <p data-lake-id="u947c853a" id="u947c853a"><span data-lake-id="u3b5665a8" id="u3b5665a8">黑色：</span><span data-lake-id="ue0cafe02" id="ue0cafe02" class="lake-fontsize-12" style="color: rgb(37, 41, 51)">该对象已经被标记过了，并且他的全部引用对象也都标记完了。</span></p>
  <p data-lake-id="u983f2ffd" id="u983f2ffd"><span data-lake-id="ue13d5c4a" id="ue13d5c4a" class="lake-fontsize-12" style="color: rgb(37, 41, 51)">​</span><br></p>
  <p data-lake-id="u6edcff24" id="u6edcff24"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1678616351411-1a4bf73b-4ddf-4eea-a630-782cba47a061.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_53%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="uca81a902" id="uca81a902"><span data-lake-id="u7aae79bd" id="u7aae79bd" class="lake-fontsize-12" style="color: rgb(37, 41, 51)">​</span><br></p>
  <p data-lake-id="u8e48b28f" id="u8e48b28f"><span data-lake-id="uddd30cd1" id="uddd30cd1">三色标记法的标记过程可以分为三个阶段：初始标记（Initial Marking）、并发标记（Concurrent Marking）和重新标记（Remark）。</span></p>
  <p data-lake-id="uba74e762" id="uba74e762"><br></p>
  <ul list="ua2f67eb9">
   <li fid="u61934708" data-lake-id="uda8a3cf3" id="uda8a3cf3"><strong><span data-lake-id="u47a699cb" id="u47a699cb">初始标记</span></strong><span data-lake-id="u860c1e17" id="u860c1e17">：遍历所有的根对象，将根对象和直接引用的对象标记为灰色。在这个阶段中，垃圾回收器只会扫描被直接或者间接引用的对象，而不会扫描整个堆。因此，初始标记阶段的时间比较短。（</span><strong><span data-lake-id="u3ed5cd05" id="u3ed5cd05">Stop The World</span></strong><span data-lake-id="ud4807a57" id="ud4807a57">）</span></li>
  </ul>
  <p data-lake-id="u3a0f6a83" id="u3a0f6a83"><span data-lake-id="u5c240cb3" id="u5c240cb3">​</span><br></p>
  <ul list="u4d5c94b1">
   <li fid="ue049174c" data-lake-id="ud9b3ce80" id="ud9b3ce80"><strong><span data-lake-id="u4c7d2ccd" id="u4c7d2ccd">并发标记</span></strong><span data-lake-id="u7afcf6a9" id="u7afcf6a9">：在这个过程中，垃圾回收器会从灰色对象开始遍历整个对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。（</span><strong><span data-lake-id="uc87fea54" id="uc87fea54">不需要STW</span></strong><span data-lake-id="u6e4c796e" id="u6e4c796e">）</span></li>
  </ul>
  <p data-lake-id="u065591bc" id="u065591bc"><br></p>
  <ul list="u4d5c94b1" start="2">
   <li fid="ue049174c" data-lake-id="u3322df6b" id="u3322df6b"><strong><span data-lake-id="ufb42de62" id="ufb42de62">重新标记</span></strong><span data-lake-id="u94ae5908" id="u94ae5908">：重新标记的主要作用是标记在并发标记阶段中被修改的对象以及未被遍历到的对象。这个过程中，垃圾回收器会从灰色对象重新开始遍历对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。（</span><strong><span data-lake-id="u2b3aa5a1" id="u2b3aa5a1">Stop The World</span></strong><span data-lake-id="u47a97c47" id="u47a97c47">）</span></li>
  </ul>
  <p data-lake-id="u819f4060" id="u819f4060"><br></p>
  <p data-lake-id="u984fe8fb" id="u984fe8fb"><span data-lake-id="u07784434" id="u07784434">在重新标记阶段结束之后，垃圾回收器会执行清除操作，将未被标记为可达对象的对象进行回收，从而释放内存空间。这个过程中，垃圾回收器会将所有未被标记的对象标记为白色（White）。</span></p>
  <p data-lake-id="ud3c0261f" id="ud3c0261f"><span data-lake-id="u1c7cc175" id="u1c7cc175">​</span><br></p>
  <p data-lake-id="u269c650d" id="u269c650d"><strong><span data-lake-id="u48645b70" id="u48645b70">以上三个标记阶段中，初始标记和重新标记是需要STW的，而并发标记是不需要STW的。其中最耗时的其实就是并发标记的这个阶段，因为这个阶段需要遍历整个对象树，而三色标记把这个阶段做到了和应用线程并发执行，大大降低了GC的停顿时长。</span></strong></p>
  <p data-lake-id="uaef7f339" id="uaef7f339"><br></p>
  <h1 data-lake-id="KuwK5" id="KuwK5"><span data-lake-id="uf4f1555d" id="uf4f1555d">扩展知识</span></h1>
  <p data-lake-id="u42cc8c4e" id="u42cc8c4e"><br></p>
  <h2 data-lake-id="CejOa" id="CejOa"><span data-lake-id="u96baa6dc" id="u96baa6dc">并发标记的写屏障</span></h2>
  <p data-lake-id="u142a14cd" id="u142a14cd"><br></p>
  <p data-lake-id="ua65e540b" id="ua65e540b"><span data-lake-id="u8d542037" id="u8d542037">并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。</span></p>
  <p data-lake-id="ubee7c7e0" id="ubee7c7e0"><span data-lake-id="ub4a9dccf" id="ub4a9dccf">​</span><br></p>
  <p data-lake-id="u1a517531" id="u1a517531"><span data-lake-id="u24ef2338" id="u24ef2338">写屏障是一种在对象引用被修改时，将其新的引用信息记录在特殊数据结构中的机制。</span><strong><span data-lake-id="u59256dd3" id="u59256dd3">在三色标记法中，写屏障技术被用于记录对象的标记状态，并且只对未被标记过的对象进行标记。</span></strong></p>
  <p data-lake-id="uac89455b" id="uac89455b"><span data-lake-id="u2378d423" id="u2378d423">​</span><br></p>
  <p data-lake-id="ub878ab41" id="ub878ab41"><span data-lake-id="ue293a0b0" id="ue293a0b0">当应用程序线程修改了一个对象的引用时，写屏障会记录该对象的新标记状态。如果该对象未被标记过，那么它会被标记为灰色，以便在垃圾回收器的下一次遍历中进行标记。如果该对象已经被标记为可达对象，那么写屏障不会对该对象进行任何操作。</span></p>
  <p data-lake-id="u57ebea7b" id="u57ebea7b"><span data-lake-id="u13c64cbd" id="u13c64cbd">​</span><br></p>
  <p data-lake-id="u1d229ca6" id="u1d229ca6"><span data-lake-id="u7e61636f" id="u7e61636f">通过使用写屏障技术，可以使得三色标记法过程中标记更加准确。然而，尽管写屏障对于维护垃圾收集器的准确性至关重要，它们仍然存在一些局限性。</span></p>
  <p data-lake-id="u3b11a01f" id="u3b11a01f"><br></p>
  <ol list="u27e1161b">
   <li fid="u25df2382" data-lake-id="u7f5f032a" id="u7f5f032a" data-lake-index-type="true"><strong><span data-lake-id="ue910f3e1" id="ue910f3e1">性能开销</span></strong><span data-lake-id="u97824798" id="u97824798">： 写屏障会引入额外的性能开销，因为每次对象引用更新时都需要执行额外的代码。这种开销可能导致系统性能下降，尤其是在高度并发的场景中。</span></li>
   <li fid="u25df2382" data-lake-id="u87b52583" id="u87b52583" data-lake-index-type="true"><strong><span data-lake-id="u66e81c3d" id="u66e81c3d">并发修改的挑战</span></strong><span data-lake-id="u16b6a9b0" id="u16b6a9b0">： 在高度并发的应用中，对象的引用可能会频繁变化。写屏障需要在每次引用变化时及时更新信息，但在极端并发条件下，可能难以捕捉到所有的变化。</span></li>
   <li fid="u25df2382" data-lake-id="ua2f5faec" id="ua2f5faec" data-lake-index-type="true"><strong><span data-lake-id="uf458a239" id="uf458a239">保守策略导致的多标</span></strong><span data-lake-id="u52160495" id="u52160495">： 为了避免误删除有效对象，一些垃圾收集器可能采取保守策略，在存在不确定性时选择保留对象。这可能导致实际上已经不再使用的对象被错误地标记为存活。</span></li>
   <li fid="u25df2382" data-lake-id="u137ad344" id="u137ad344" data-lake-index-type="true"><strong><span data-lake-id="ua52e3c24" id="ua52e3c24">优化策略的双刃剑</span></strong><span data-lake-id="uc45f5596" id="uc45f5596">： 为了减轻性能开销，某些垃圾收集器可能采用优化策略，例如只在特定条件下激活写屏障。这种优化有可能导致某些引用更新被错过，影响标记的准确性。</span></li>
  </ol>
  <p data-lake-id="u7eca6448" id="u7eca6448"><span data-lake-id="uea6ac3ea" id="uea6ac3ea">​</span><br></p>
  <p data-lake-id="u95df05bb" id="u95df05bb"><span data-lake-id="u22cca737" id="u22cca737">所以，三色标记法即使在并发标记过程中用了写屏障，还是可能会带来多标和少标的问题。</span></p>
  <p data-lake-id="uc3b52ad4" id="uc3b52ad4"><br></p>
  <h2 data-lake-id="cUweE" id="cUweE"><span data-lake-id="u9febdb8d" id="u9febdb8d">多标的问题</span></h2>
  <p data-lake-id="ua3e01998" id="ua3e01998"><br></p>
  <p data-lake-id="u43204049" id="u43204049"><span data-lake-id="u97dbdb5e" id="u97dbdb5e">所谓多标，其实就是这个对象原本应该被回收掉的白色对象，但是被错误的标记成了黑色的存活对象。从而导致这个对象没有被GC回收掉。</span></p>
  <p data-lake-id="uce03f02a" id="uce03f02a"><span data-lake-id="uee5f0271" id="uee5f0271">​</span><br></p>
  <p data-lake-id="ue2769bfb" id="ue2769bfb"><span data-lake-id="u871b678f" id="u871b678f">这个一般发生在并发标记过程中，该对象还是有引用的，但是在过程中，应用程序执行过程中把他的引用关系删除了，导致他变成了一个垃圾对象。</span></p>
  <p data-lake-id="ucd8d5c8c" id="ucd8d5c8c"><span data-lake-id="u938182a9" id="u938182a9">​</span><br></p>
  <p data-lake-id="u66e6be24" id="u66e6be24"><span data-lake-id="u36edab33" id="u36edab33">多标的话，会产生</span><strong><span data-lake-id="udfa5e2d8" id="udfa5e2d8">浮动垃圾</span></strong><span data-lake-id="ufd6562ca" id="ufd6562ca">，这个问题一般都不太需要解决，因为这种垃圾一般都不会太多，另外在下一次GC的时候也都能被回收掉。</span></p>
  <p data-lake-id="ub30a3e6b" id="ub30a3e6b"><br></p>
  <h2 data-lake-id="W8DcO" id="W8DcO"><span data-lake-id="u159d8ecd" id="u159d8ecd">怎么解决漏标的问题</span></h2>
  <p data-lake-id="u4c6c9c80" id="u4c6c9c80"><br></p>
  <p data-lake-id="u0ed13e56" id="u0ed13e56"><span data-lake-id="u9d688c81" id="u9d688c81">所谓漏标，和多标刚好相反，就是说一个对象本来应该是黑色存活对象，但是没有被正确的标记上，导致被错误的垃圾回收掉了。</span></p>
  <p data-lake-id="ua058037c" id="ua058037c"><span data-lake-id="u2bf5d963" id="u2bf5d963">​</span><br></p>
  <p data-lake-id="uaaeab0f9" id="uaaeab0f9"><span data-lake-id="u9c1b6667" id="u9c1b6667">这种情况一旦发生是很危险的，一个正常使用的对象被垃圾回收掉了，这对系统来说是灾难性的问题，那么如何解决呢？</span></p>
  <p data-lake-id="u6583fd91" id="u6583fd91"><span data-lake-id="u943ad2e1" id="u943ad2e1">​</span><br></p>
  <p data-lake-id="u89b7c6eb" id="u89b7c6eb"><span data-lake-id="ueb48a76a" id="ueb48a76a">具体的解决方式，在CMS和G1中也不太一样。</span><strong><span data-lake-id="u5a03b6eb" id="u5a03b6eb">CMS采用的是增量更新方案，G1则采用的是原始快照的方案。</span></strong></p>
  <p data-lake-id="ue1c14f57" id="ue1c14f57"><span data-lake-id="uc12b3c2b" id="uc12b3c2b">​</span><br></p>
  <p data-lake-id="u8fe08640" id="u8fe08640"><span data-lake-id="u1cbb7d0b" id="u1cbb7d0b">漏标的问题想要发生，需要同时满足两个充要条件：</span></p>
  <p data-lake-id="uc30d874a" id="uc30d874a"><span data-lake-id="u70dcbf71" id="u70dcbf71">​</span><br></p>
  <p data-lake-id="u9684b512" id="u9684b512"><span data-lake-id="u41356c62" id="u41356c62">1、至少有一个黑色对象在自己被标记之后指向了这个白色对象</span></p>
  <p data-lake-id="u59825a5a" id="u59825a5a"><span data-lake-id="uf0e460dc" id="uf0e460dc">2、所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用</span></p>
  <p data-lake-id="u0060c85c" id="u0060c85c"><span data-lake-id="uf3b42936" id="uf3b42936">​</span><br></p>
  <p data-lake-id="u0f8cd933" id="u0f8cd933"><span data-lake-id="u93993bab" id="u93993bab">那么，增量更新方案就是破坏了第一个条件，而原始快照方案就是破坏了第二个条件。</span></p>
  <p data-lake-id="u30f002b3" id="u30f002b3"><span data-lake-id="u355824ea" id="u355824ea">​</span><br></p>
  <h3 data-lake-id="o53pX" id="o53pX"><span data-lake-id="u40940589" id="u40940589">增量更新</span></h3>
  <p data-lake-id="u979870be" id="u979870be"><br></p>
  <p data-lake-id="u02c3628a" id="u02c3628a"><span data-lake-id="ubd027db5" id="ubd027db5">“至少有一个黑色对象在自己被标记之后指向了这个白色对象”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：</span></p>
  <p data-lake-id="u2a410968" id="u2a410968"><span data-lake-id="u52b4f000" id="u52b4f000">​</span><br></p>
  <p data-lake-id="ud4466e5d" id="ud4466e5d"><span data-lake-id="u48f12c78" id="u48f12c78">如果有黑色对象在自己标记后，又重新指向了白色对象。那么我就把这个黑色对象的引用记录下来，在后续「重新标记」阶段再以这个黑色对象为根，对其引用进行重新扫描。通过这种方式，被黑色对象引用的白色对象就会变成灰色，从而变为存活状态。</span></p>
  <p data-lake-id="uc5d9c104" id="uc5d9c104"><span data-lake-id="u1ef161e1" id="u1ef161e1">​</span><br></p>
  <p data-lake-id="u0fd8cf2c" id="u0fd8cf2c"><span data-lake-id="u519ffc86" id="u519ffc86">这种方式有个缺点，就是会重新扫描新增的这部分黑色对象，会浪费多一些时间。但是其实这个浪费还好，因为本来这种漏标的情况就并不是特别常见，所以这部分需要重新扫描的黑色对象也并不多。</span></p>
  <p data-lake-id="u73d8a01b" id="u73d8a01b"><br></p>
  <h3 data-lake-id="japEJ" id="japEJ"><span data-lake-id="ud3e6f493" id="ud3e6f493">原始快照</span></h3>
  <p data-lake-id="u756f0d7b" id="u756f0d7b"><br></p>
  <p data-lake-id="uc4f22efb" id="uc4f22efb"><span data-lake-id="uf5108059" id="uf5108059">"所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用"，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：</span></p>
  <p data-lake-id="u06ae4c73" id="u06ae4c73"><br></p>
  <p data-lake-id="u6a4fa27d" id="u6a4fa27d"><span data-lake-id="u1dac0db0" id="u1dac0db0">如果灰色对象在扫描完成前删除了对白色对象的引用，那么我们就在灰色对象取消引用之前，先将灰色对象引用的白色对象记录下来。</span></p>
  <p data-lake-id="ud2da1447" id="ud2da1447"><span data-lake-id="uc9377358" id="uc9377358">​</span><br></p>
  <p data-lake-id="u6a5951ac" id="u6a5951ac"><span data-lake-id="u328b71d7" id="u328b71d7">在后续「重新标记」阶段再以这些白色对象为根，对它的引用进行扫描，从而避免了漏标的问题。通过这种方式，原本漏标的对象就会被重新扫描变成灰色，从而变为存活状态。</span></p>
  <p data-lake-id="u8a4764ff" id="u8a4764ff"><span data-lake-id="u4b37af32" id="u4b37af32">​</span><br></p>
  <p data-lake-id="udc15d0c3" id="udc15d0c3"><span data-lake-id="u51a87029" id="u51a87029">但是这种方式可能会把本来真的要取消引用的对象给错误的复活了，从而产生浮动垃圾。但是就像前面说的，多标的问题是可以忽略的。</span></p>
  <p data-lake-id="uc7738aef" id="uc7738aef"><span data-lake-id="u90c8b29a" id="u90c8b29a">​</span><br></p>
  <p data-lake-id="u26378992" id="u26378992"><span data-lake-id="ud5a03278" id="ud5a03278">​</span><br></p>
  <p data-lake-id="uf8526d9d" id="uf8526d9d"><span data-lake-id="u7fefc211" id="u7fefc211">​</span><br></p>
  <p data-lake-id="u3daa0145" id="u3daa0145"><span data-lake-id="u3431412d" id="u3431412d">​</span><br></p>
 </body>
</html>